#include <AVL.h>


int getHeight(AVLNode* node) {
    return node ? node->height : 0;
}

int getBalance(AVLNode* node) {
    return node ? getHeight(node->left) - getHeight(node->right) : 0;
}

void updateHeight(AVLNode* node) {
    int leftHeight = getHeight(node->left);
    int rightHeight = getHeight(node->right);
    node->height = (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}


AVLNode* rightRotate(AVLNode* y) {
    AVLNode* x = y->left;
    AVLNode* T2 = x->right;

    // 执行右旋
    x->right = y;
    y->left = T2;

    // 更新高度
    updateHeight(y);
    updateHeight(x);

    return x;
}

AVLNode* leftRotate(AVLNode* x) {
    AVLNode* y = x->right;
    AVLNode* T2 = y->left;

    // 执行左旋
    y->left = x;
    x->right = T2;

    // 更新高度
    updateHeight(x);
    updateHeight(y);

    return y;
}

AVLNode* insert(AVLNode* node, int key) {
    // 1. 正常二叉搜索树的插入
    if (node == NULL) {
        return (AVLNode*)malloc(sizeof(AVLNode));
    } else if (key < node->key) {
        node->left = insert(node->left, key);
    } else if (key > node->key) {
        node->right = insert(node->right, key);
    } else {
        // key已存在，不插入
        return node;
    }

    // 2. 更新节点的高度
    updateHeight(node);

    // 3. 获取平衡因子
    int balance = getBalance(node);

    // 如果平衡因子大于1，进行以下四种情况的调整
    if (balance > 1) {
        if (key < node->left->key) {
            // 左-左情况
            return rightRotate(node);
        } else {
            // 左-右情况
            node->left = leftRotate(node->left);
            // 调整为右旋
            return rightRotate(node);
        }
    }

    // 如果平衡因子小于-1，进行以下四种情况的调整
    if (balance < -1) {
        if (key > node->right->key) {
            // 右-右情况
            return leftRotate(node);
        } else {
            // 右-左情况
            node->right = rightRotate(node->right);
            // 调整为左旋
            return leftRotate(node);
        }
    }

    // 返回未改变的节点指针
    return node;
}

void preOrder(AVLNode* node) {
    if (node != NULL) {
        printf("%d ", node->key);
        preOrder(node->left);
        preOrder(node->right);
    }
}

int main() {
    AVLNode* root = NULL;
    root = insert(root, 10);
    root = insert(root, 20);
    root = insert(root, 30);
    root = insert(root, 40);
    root = insert(root, 50);
    root = insert(root, 25);

    printf("Pre-Order traversal of the constructed AVL tree is: ");
    preOrder(root);
    printf("\n");

    return 0;
}



